#include<stdio.h>
#include<stdlib.h>
#define MAX_LEN 12

void swp(int arr[],int i,int j){
	int t = arr[i];
	arr[i] = j;
	if(i < j)
		arr[i+1] = arr[j];
	arr[j] = t;
}

void islegal(int arr[],int N){
	int j=1,top=0,res=0;
	int x = 1,y = arr[j];
	int stack[MAX_LEN];
	while(x<N || j<=N){
		if(y == 0){
			res = 1;
			break;
		}
		if(y==x){
			x++;
			y = arr[++j];
	   	}else if(top > 0 && y == stack[top-1]){
			top--;
			y = arr[++j];
	   	}else if(x < N){
			stack[top++] = x++;
	   	}else{
			break;
		}
	}
	
	if(res){
		for(j=1;j<N;j++){
		    printf("%d",arr[j]);
		}
		printf("\n");
	}
}

void foo(int a[],int N,int MAX_NUM){
	if(MAX_NUM == 1){
	    printf("%d\n",a[1]);
	    return ;
	}
	if( N >= MAX_NUM )
	    return;
	int i,j;
	int arr[MAX_LEN];
	for(j=0;j<MAX_LEN;j++){
		arr[j] = a[j];
	}
	arr[N+1] = N+1;
	arr[N+2] = 0;
	for(i=N+1;i>0;i--){
		swp(arr,i,N+1);
		if( N + 1 == MAX_NUM)
			islegal(arr,N+2);
		foo(arr,N+1,MAX_NUM);
	}
}

int main(){
	int arr[MAX_LEN] = {0,1,0,0,0,0,0,0,0,0,0,0};
	int N,MAX_NUM;
	scanf("%d",&N);
	while(N--){
		scanf("%d",&MAX_NUM);
		foo(arr,1,MAX_NUM);
	}
	return 0;
}
